import java.util.ArrayList;
import java.util.Random;



/** Cette classe correspond à la définition de la colonie de fourmis
 * qui déterminera le plus court chemin pour notre problème.
 * @author Pocman
 *
 */

public class AntColony {
	protected static final double ALPHA = 0.1; //parametre d'évaporation pour la mise à jour globale
	private Ant[] ants;
	private int nbAnts;
	private int nbIterations;
	private int nbSommet;
	public static int nbNoeudsVoisins = 40;
	private int compteur;
	private AntInstance antInstance;
	public int iterationRenforcement;
	private ArrayList<Boolean> renforcement;
	public static double min = 0.5;
	public static double max = 0.8;
	private AntListeCandidat listeCandidat;
	long m_time;
	private ArrayList<Double> meilleursCheminsIterations;
	private double minimumIterationDepuisReinitialisation;
	private AntSolution meilleurIterationDepuisReinitialisation;
	private int stagne; 
	private boolean[] dontLookBit;
	
	
	private static final Random r = new Random(System.currentTimeMillis());
	/** Constructeur de la colonie de fourmis
	 * 
	 */
    public AntColony(Instance instance, int nbAnts, int iterations, long m_time) throws Exception
    {	
    	this.compteur = 0;
    	this.antInstance = new AntInstance (instance);
    	this.nbAnts = nbAnts;
    	this.nbIterations = iterations;
    	this.m_time = m_time;
    	this.meilleursCheminsIterations = new ArrayList<Double>(); 
    	this.stagne =0;
    	this.minimumIterationDepuisReinitialisation = Double.MAX_VALUE;
    	this.meilleurIterationDepuisReinitialisation = null;
    	
        AntListeCandidat.initialisationListeCandidat(this.antInstance);
        this.listeCandidat=new AntListeCandidat();
        this.listeCandidat.setNbNoeudsVoisins(nbNoeudsVoisins);
        
        Ant.setAntInstance(this.antInstance);
        Ant.setAntColony(this);
        this.ants = new Ant[this.nbAnts];
        for(int i = 0; i < this.nbAnts; i++)
        {
            ants[i] = new Ant();
        }
        nbSommet = this.antInstance.getInstance().getNbSommets();     
        this.dontLookBit = new boolean[this.nbSommet];
    
    }
    
    /** Algorithme Start
     * Déroulement du comportement du programme en fonction du temps passé, du nombre d'iterations et de la distance miniamle trouvee
     * @throws Exception
     */
    public void start() throws Exception{
    	int iterations = 0;
    	this.reinitialiserAlternanceRenforcement();
    	
    	long tempsFourmies = 0;
    	long tempsDeuxOpt = 0;
    	long tempsMiseAJourFinTournee = 0;
    	long tempsBoucle = 0;
    	long debutTempsActuel = System.currentTimeMillis();
    	long tempsActuel = 0;
    	
    	while(((tempsActuel)<(m_time*1000-2*tempsBoucle))&&(iterations < this.nbIterations)){
    		
    		long debutBoucle = System.currentTimeMillis();

    		for(int i = 0; i < ants.length; i++){
    			ants[i].start();
    		}
    		iterations++;
    		for(int i = 0; i < ants.length; i++){
    			ants[i].getThread().join();
    		}
    		
    		if(tempsFourmies == 0)
    			tempsFourmies = System.currentTimeMillis();
    		
    		meilleursCheminsIterations.add(Ant.meilleurCheminIteration.getLongueurSolution()); 			
    		
    		Ant.miseAJourFinTournee(this.renforcement.get(this.iterationRenforcement));
    		this.iterationRenforcement++;
    		
       		if(Ant.miseAJourMeilleurChemin()){
       			System.err.println("\n longueur meilleur chemin : " + Ant.meilleurChemin.getLongueurSolution() +" pour itération n° :" + iterations);
    			this.antInstance.limitationDesPheromones();
    			this.stagne = 0;
    		}    		    		
   		
			if (reinitialisation(iterations, renforcement.get(iterationRenforcement))) {
				Ant.miseAJourMeilleurChemin();
				System.err.println("++++++++++++++++++++++++");
				System.err.println("++++++++++++++++++++++++");
				this.antInstance.initialiserTau();
				reinitialiserAlternanceRenforcement();
				this.iterationRenforcement = 0;
				this.minimumIterationDepuisReinitialisation = Double.MAX_VALUE;
				this.meilleurIterationDepuisReinitialisation = null;
			}
			else{
				if(Ant.miseAJourMeilleurChemin())
	    			this.antInstance.limitationDesPheromones();
			}
		//	System.err.println("longueur meilleur chemin iteration : " + Ant.meilleurCheminIteration.getLongueurSolution() +" pour itération n° :" + iterations);
    		
    	//	System.err.println("longueur meilleur chemin : " + Ant.meilleurChemin.getLongueurSolution() +" pour itération n° :" + iterations);
    		  
    		long finBoucle = System.currentTimeMillis();
    		
    		tempsActuel = finBoucle - debutTempsActuel;
    		
    		long ancienTempsBoucle = tempsBoucle;
    		tempsBoucle = finBoucle - debutBoucle;
    		
    		if(tempsBoucle<ancienTempsBoucle){
    			tempsBoucle = ancienTempsBoucle;
    		}
    	}
    	System.err.println("longueur meilleur chemin de l'itération : " + Ant.meilleurCheminIteration.getLongueurSolution() );
		System.err.println("longueur meilleur chemin : " + Ant.meilleurChemin.getLongueurSolution() +" pour itération n° :" + iterations);
		System.err.println("temps boucle fourmies:" + tempsFourmies);
		System.err.println("temps boucle :" + tempsBoucle);
    }
     /** Fonction stagnation
      * Comparaison entre les chemins calcules aux differentes iterations
      * retourne un booleen vrai si la solution stagne pendant 15 iterations
      */
    public boolean stagnation(boolean utilCheminIteration, int iteration){
    	if((this.minimumIterationDepuisReinitialisation == Double.MAX_VALUE) || Ant.meilleurCheminIteration.isBest(meilleurIterationDepuisReinitialisation)){
    		this.minimumIterationDepuisReinitialisation = Ant.meilleurCheminIteration.getLongueurSolution();
    		this.meilleurIterationDepuisReinitialisation = Ant.meilleurCheminIteration;
    	}
    	
    	if(!utilCheminIteration && iteration>1  && !Ant.meilleurCheminIteration.isBest(meilleurIterationDepuisReinitialisation)){
    		stagne++;
    		System.err.print(stagne + "/");
    	}else if(iteration>1 &&  Ant.meilleurCheminIteration.isBest(meilleurIterationDepuisReinitialisation)){
    		stagne = 0;
    		System.err.println(stagne + "/");
    	}
    	
    	if(stagne > 30){
    		stagne = 0 ;
    		return true;
    	}else{
    		return false;
    	}
    	
    }
    /**Fonction amelioration
     * retourne un booleen vrai s'il y a une amelioration entre l'iteration n-2 et n-1
     */
    public boolean amelioration (int iteration, ArrayList<Double> mci ){
    	if(mci.get(iteration-2)>mci.get(iteration-1)){
    		return true;
    	}else{
    		return false;
    	}
    }
    
    /** Fonction reinitialisation
     * reinitialise la variable meilleurCheminIteration à celle de l'iteration n-1
     * retourne un booleen vrai si le meilleurCheminIteration est superieur au meilleur chemin depuis la reinitialisation et que stagnation est vrai
     * un booleen faux sinon
     */
    public boolean reinitialisation (int iteration, boolean renforcement){
    	if(stagnation(renforcement,iteration)){
    		try {
    			Ant.meilleurCheminIteration = this.meilleurIterationDepuisReinitialisation;
    			System.err.println("		longueur meilleur chemin de l'itération avant 3opt : " + Ant.meilleurCheminIteration.getLongueurSolution() );
					troisOpt();
				System.err.println("		longueur meilleur chemin de l'itération après 3opt : " + Ant.meilleurCheminIteration.getLongueurSolution() );
				this.meilleursCheminsIterations.remove(iteration-1);
				meilleursCheminsIterations.add(Ant.meilleurCheminIteration.getLongueurSolution()); 
			} catch (Exception e) {
				e.printStackTrace();
			}
   			if(Ant.meilleurCheminIteration.isBest(this.meilleurIterationDepuisReinitialisation)){
   				this.minimumIterationDepuisReinitialisation = Ant.meilleurCheminIteration.getLongueurSolution();
   	    		this.meilleurIterationDepuisReinitialisation = Ant.meilleurCheminIteration;
   				return false;
   			}else{
   				return true;
   			}
   		}else{
    		return false;
    	}	
    }
    
    
    /**Algorithme du 2-OPT
     * Ameliore le chemin le plus court en echangeant l'ordre de parcours de 2 points
     * 1 seul cas possible
     * Utilisation des dontLookBits et des noeuds voisins
     * @throws Exception
     */
    public void deuxOpt(AntSolution s) throws Exception {
		boolean amelioration = true;
		
		for(int i = 0; i < dontLookBit.length; i++)
			dontLookBit[i] = false;
		while(amelioration){
			amelioration = false;
		for (int i = 0; i < nbSommet; i++) {
			if(!dontLookBit[i]){
				dontLookBit[i] = true;
			for (int n = 0; n < this.listeCandidat.getNbNoeudsVoisins(); n++) {
				int j = this.listeCandidat.getNoeudSuivant(i, n);
				if (s.getDistance(i, i + 1) + s.getDistance(j, j + 1) > s.getDistance(i, j) + s.getDistance(i + 1, j + 1)) {
					s.inverserArcs(i+1, j);
					amelioration = true;
						dontLookBit[i] = false;
						dontLookBit[j] = false;
				}
			}
			}
		}
		}
	}

    /**Algorithme 3-OPT
     * ameliore le chemin le plus court en changeant le sens de parcours de certains arcs, en insérant des arcs entre d'autres.
     * Seul cas etudie : i<j<k
     * 4 cas concernes : e, f, g, h
     * Utilisation des dontLookBits
     * @throws Exception
     */
	public void troisOpt() throws Exception {
		AntSolution s = Ant.meilleurCheminIteration;
		for(int i = 0; i < dontLookBit.length; i++)
			dontLookBit[i] = false;
		
		boolean amelioration = true;
		while (amelioration) {
			amelioration = false;
		System.err.print("|");
			for (int i = 1; i < this.nbSommet - 4; i++) {
				if(!dontLookBit[i]){
					dontLookBit[i] = true;
				for (int j = i + 2; j < this.nbSommet - 2; j++) {
					if(!dontLookBit[j]){
						dontLookBit[j] = true;
					for (int k = j + 2; k < this.nbSommet; k++) {
						
						double distanceInit = s.getDistance(i, i + 1)
								+ s.getDistance(j, j + 1)
								+ s.getDistance(k, k + 1);
						// h ===> �a marche
						if (distanceInit > s.getDistance(i, j + 1)
								+ s.getDistance(i + 1, k)
								+ s.getDistance(j, k + 1)) {
							s = s.insererArcs(i, j + 1, k);
							Ant.meilleurCheminIteration = s;
							System.err.print("h");
							amelioration = true;
							dontLookBit[i] = false;
							dontLookBit[j] = false;
//							dontLookBit[j+1] = false;
//							dontLookBit[k+1] = false;
							dontLookBit[k] = false;
						}
						// e ===> �a marche
						else if (distanceInit > s.getDistance(i, k)
								+ s.getDistance(i + 1, j + 1)
								+ s.getDistance(j, k + 1)) {
							s.inverserArcs(j + 1, k);
							s = s.insererArcs(i, j + 1, k);
							Ant.meilleurCheminIteration = s;
							System.err.print("e");
							amelioration = true;
							
							dontLookBit[i] = false;
							dontLookBit[j] = false;
//							dontLookBit[j+1] = false;
//							dontLookBit[k+1] = false;
						}
						// f ===> �a marche
						else if (distanceInit > s.getDistance(i, j + 1)
								+ s.getDistance(k, j)
								+ s.getDistance(i + 1, k + 1)) {
							s.inverserArcs(i + 1, j);
							s = s.insererArcs(i, j + 1, k);
							Ant.meilleurCheminIteration = s;
							System.err.print("f");
							amelioration = true;
							

							dontLookBit[i] = false;
							dontLookBit[j] = false;
//							dontLookBit[j+1] = false;
//							dontLookBit[k+1] = false;
						}
						// g ===> �a marche
						else if (distanceInit > s.getDistance(i, j)
								+ s.getDistance(i + 1, k)
								+ s.getDistance(j + 1, k + 1)) {
							s.inverserArcs(i + 1, j);
							s.inverserArcs(j + 1, k);
							System.err.print("g");
							amelioration = true;
							

							dontLookBit[i] = false;
							dontLookBit[j] = false;
//							dontLookBit[k+1] = false;
							dontLookBit[k] = false;
							
						}
						

					}
				}}
			}}

		}
//		System.err.println("");
	}
	
	/** Fonction reinitialiserAlternanceRenforcement
	 * ajoute un true à l'arrayList de booleens renforcement, si le prochain nombre est supérieur à la proportion 
	 */
	public void reinitialiserAlternanceRenforcement(){
    	iterationRenforcement = 0;
    	renforcement = new ArrayList<Boolean>();
    	renforcement.add(true);
    	for(int i = 0; i < 25; i++)
    		renforcement.add(true);   
    	
    	for(int i = 0; i < 50; i++){
    		if(r.nextDouble() > 0.20) //0.2
    			renforcement.add(true);
    		else 
    			renforcement.add(false);
    	}
    	
    	for(int i = 0; i < 50; i++){
    		if(r.nextDouble() > 0.33) //0.33
    			renforcement.add(true);
    		else 
    			renforcement.add(false);
    	}	
    	
    	for(int i = 0; i < 100; i++){
    		if(r.nextDouble() > 0.5) //0.5
    			renforcement.add(true);
    		else 
    			renforcement.add(false);
    	}	
    	for(int i = 0; i < this.nbIterations - 175; i++){
    		if(r.nextDouble() > 0.9)
    			renforcement.add(true);
    		else 
    			renforcement.add(false);
    	}	
    }

    public Solution getMeilleurChemin(){
    	return Ant.meilleurChemin.getSolution();
    }
//	public void troisOpt() throws Exception {
//	AntSolution s = Ant.meilleurCheminIteration;
//	
//	for(int i = 0; i < dontLookBit.length; i++)
//		dontLookBit[i] = false;
//	
//	boolean amelioration = true;
//	int compteur = 0;
//	System.err.print("|");
//	while (amelioration) {
//	amelioration = false;
//		for (int i = 0; i < this.nbSommet; i++) {
//			System.err.print(" " + compteur);
//			for (int n = 0; n < this.listeCandidat.getNbNoeudsVoisins(); n++) {
//				int j = this.listeCandidat.getNoeudSuivant(i, n);
////				if(i > j){
////					int tmp = i;
////					i = j;
////					j = tmp;
////					//System.err.print("i");
////				}
//				
//				if(!dontLookBit[i] && j > i + 1){
//					dontLookBit[i] = true;
//					compteur++;
//				for (int m = 0; m < this.listeCandidat.getNbNoeudsVoisins(); m++) {
//					
//					int k = this.listeCandidat.getNoeudSuivant(j, m);
////					if(k < i){
////						int tmp = k;
////						k = j;
////						j = i;
////						i = tmp;
////					}
////					else if(k < j){
////						int tmp = k;
////						k = j;
////						j = tmp;							
////					}
//					
//					if(!dontLookBit[j] && k > j+1){
//						dontLookBit[j] = true;
//					double distanceInit = s.getDistance(i, i + 1)
//							+ s.getDistance(j, j + 1)
//							+ s.getDistance(k, k + 1);
//					
//					// h ===> �a marche
//					if (distanceInit > s.getDistance(i, j + 1)
//							+ s.getDistance(i + 1, k)
//							+ s.getDistance(j, k + 1)) {
//						s = s.insererArcs(i, j + 1, k);
//						Ant.meilleurCheminIteration = s;
//						System.err.print("h");
//						amelioration = true;
//						dontLookBit[i] = false;
//						dontLookBit[j] = false;
//						dontLookBit[k] = false;
//					}
//					
//					// e ===> �a marche
//					else if (distanceInit > s.getDistance(i, k)
//							+ s.getDistance(i + 1, j + 1)
//							+ s.getDistance(j, k + 1)) {
//						s.inverserArcs(j + 1, k);
//						s = s.insererArcs(i, j + 1, k);
//						Ant.meilleurCheminIteration = s;
//						System.err.print("e");
//						amelioration = true;
//						dontLookBit[i] = false;
//						dontLookBit[j] = false;
//						dontLookBit[k] = false;
//					}
//					// f ===> �a marche
//					else if (distanceInit > s.getDistance(i, j + 1)
//							+ s.getDistance(k, j)
//							+ s.getDistance(i + 1, k + 1)) {
//						s.inverserArcs(i + 1, j);
//						s = s.insererArcs(i, j + 1, k);
//						Ant.meilleurCheminIteration = s;
//						System.err.print("f");
//						amelioration = true;
//						dontLookBit[i] = false;
//						dontLookBit[j] = false;
//						dontLookBit[k] = false;
//					}
//					// g ===> �a marche
//					else if (distanceInit > s.getDistance(i, j)
//							+ s.getDistance(i + 1, k)
//							+ s.getDistance(j + 1, k + 1)) {
//						s.inverserArcs(i + 1, j);
//						s.inverserArcs(j + 1, k);
//						System.err.print("g");
//						amelioration = true;
//						dontLookBit[i] = false;
//						dontLookBit[j] = false;
//						dontLookBit[k] = false;
//					}
//					
//					
//					}
//				}
//			}
//			}
//
//		}
//
//	}
//	System.err.println("");
//}
}
